Tolerancia a fallos
El método más usado en tolerancia a fallos es el empleo de redundancia
La redundancia puede ser:
de información: p.ej. añadiendo bits con código de Hamming que permita recuperar errores
de tiempo: se realiza una acción, y en caso necesario, se repite en el tiempo. P.ej. la transacción atómica. La redundancia en el tiempo es muy útil en fallos intermitentes y transitorios
física: se agregan equipos o procesadores adicionales. Se puede hacer de dos formas:
réplica activa
respaldo primario
Tolerancia a fallos
Tolerancia a fallos mediante réplica activa: todos los procesadores se usan todo el tiempo como servidores, funcionando en paralelo, ocultando los fallos
La réplica activa se utiliza en:
biología: los mamíferos tenemos dos ojos, oídos, etc.
aviación: los 747 tienen 4 motores pero pueden volar con 3
deporte: varios árbitros
Se dice que un sistema es tolerante a k fallos si puede superar fallos en k componentes y seguir cumpliendo sus especificaciones
Tolerancia a fallos
Si los componentes fallan de manera silenciosa, bastan k+1 de ellos para proporcionar la tolerancia a k fallos
Si los componentes tienen fallos bizantinos, continuan su ejecución al fallar y dan respuestas aleatorias o erróneas, por lo que se necesitan al menos 2k+1 componentes para lograr la tolerancia a k fallos
Tolerancia a fallos
Tolerancia a fallos mediante respaldo primario: en todo instante es un servidor primario el que realiza todo el trabajo. Si el primario falla, el de respaldo comienza a funcionar, todo ello de forma transparente a los programas de aplicación
De este esquema también hay numerosos ejemplos en la vida real:
gobierno: ej. vicepresidente
aviación: ej. copilotos
generadores diesel en los hospitales
Ventaja con respecto a la réplica activa: la operación normal es más sencilla, funciona solo un servidor en vez de varios en paralelo
Desventaja: trabaja mal en presencia de fallos bizantinos, en los que el primario afirma erróneamente que funciona de manera perfecta
Tolerancia a fallos
Acuerdos en sistemas defectuosos: en ss.dd. es muy importante lograr acuerdos sobre algo (elección de coordinador, si completar una transacción o no). ¿cómo llegar a acuerdos cuando hay fallos?
Supongamos que tenemos procesadores perfectos pero una línea de comunicación que puede fallar
Ese caso podemos estudiarlo teóricamente con el problema de los dos ejércitos
Tolerancia a fallos
Problema de los dos ejércitos:
El ejército rojo tiene 5000 soldados, acampados en un valle
Dos ejércitos azules, cada uno con 3000 efectivos, acampan en las colinas circundantes al valle
Si los dos ejércitos azules logran llegar a un acuerdo de ataque simultáneo, derrotarán al ejército rojo
Si solo lo intenta uno de los ejércitos azules, saldrá derrotado
Supongamos que el comandante del ejército 1 envía un mensaje al comandante del ejército 2. El mensaje dice “Tengo un plan, ataquemos mañana al amanecer”
El mensajero logra pasar, y el comandante del ejército 2 le devuelve una nota que dice “Espléndido, ataquemos pues mañana al amanecer”
El mensajero regresa a salvo y el comandante 1 prepara entonces a sus tropas
Tolerancia a fallos
Pero más tarde el comandante 1 se pone a pensar y se da cuenta de que el comandante 2 no sabe si el mensajeró regresó a salvo, y al dudar podría no atreverse a atacar
Así que el comandante 1 vuelve a enviar un mensaje
Ocurre lo mismo
No importa el nº de reconocimientos enviados, el comandante 1 y el comandante 2 nunca llegarán a un acuerdo
=> Incluso si los procesadores no fallan (comandantes), el acuerdo entre dos procesos no es posible si existe una comunicación no confiable
Tolerancia a fallos
Supongamos ahora que la comunicación es perfecta pero los procesadores no lo son
Ese caso podemos estudiarlo teóricamente con el problema de los generales bizantinos
El ejército rojo sigue acampando en el valle, pero n generales azules comandan ejércitos en las colinas cercanas
La comunicación es perfecta (p.ej línea telefónica), pero m de los n generales son traidores (fallan). Dan información incorrecta o contradictoria
Ahora supongamos que cada general conoce el nº de soldados de que dispone. Definiremos el acuerdo como sigue: los generales intercambian la información del nº de soldados que tienen. Al final del algoritmo cada general debe tener un vector de longitud n. Si el general i es leal, entonces el elemento i es su cantidad de efectivos; en caso contrario está indefinido
Tolerancia a fallos
Lamport y colaboradores diseñaron un algoritmo recursivo que resuelve este problema bajo ciertas condiciones
Veamos cómo funciona para n=4 y m=1 (tres generales leales y uno traidor). Con estos parámetros el algoritmo opera en 4 pasos
En el paso uno, cada general envía un mensaje a los demás con la información de sus tropas
Los generales leales dicen la verdad, mientras que el traidor puede decir a cada uno de los demás una mentira diferente. Sea el general 3 el traidor. Informan así:
general 1: 1 Ksoldados
general 2: 2 Ksoldados
general 3: x,y,z Ksoldados
general 4: 4 Ksoldados
Tolerancia a fallos
En el paso 2, los resultados recibidos de los otros se reunen en forma de vectores:
1. (1,2,x,4)
2. (1,2,y,4)
3. (1,2,3,4)
4. (1,2,z,4)
En el paso 3, cada general pasa su vector a los demás
En este paso el general 3 vuelve a mentir, ideando 12 nuevos valores a-l:
gral.1 gral.2 gral.4
(1,2,y,4) (1,2,x,4) (1,2,x,4)
(a,b,c,d) (e,f,g,h) (1,2,y,4)
(1,2,z,4) (1,2,z,4) (i,j,k,l)
Tolerancia a fallos
Por último, en el paso 4 cada general examina su i-ésimo elemento de cada uno de los vectores que ha recibido
Si cualquier valor tiene una mayoría, este valor se coloca en el vector resultado. Si ningún valor tiene mayoría, el elemento correspondiente del vector resultado se marca como INCOGNITA
Vemos que en este caso obtenemos como vector resultado:
(1,2,INCOGNITA,4)
=> El general 3 es un traidor!
Tolerancia a fallos
Lamport y colaboradores demostraron que en un sistema con m procesadores que pueden fallar, el acuerdo solo se logra si se dispone de 2m+1 procesadores que funcionen de manera correcta
Si por ejemplo hubiésemos tenido n=3 y m=1 (dos generales leales y un traidor) no hubiésemos podido llegar a un acuerdo
 Página anterior | Volver al principio del trabajo | Página siguiente  |